package com.lw.leetcode.back.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 127. 单词接龙
 * 剑指 Offer II 108. 单词演变
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/1 10:35
 */
public class LadderLength {


    public static void main(String[] args) {
        LadderLength test = new LadderLength();

        // 5
//        String beginWord = "hit";
//        String endWord = "cog";
//        List<String> list = Arrays.asList("hot","dot","dog","lot","log","cog");

        // 0
        String beginWord = "hit";
        String endWord = "cog";
        List<String> list = Arrays.asList("hot", "dot", "dog", "lot", "log");

        int i = test.ladderLength(beginWord, endWord, list);
        System.out.println(i);
    }


    private Set<String> set = new HashSet<>();

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            return 0;
        }
        set.addAll(wordList);
        if (!set.contains(endWord)) {
            return 0;
        }
        LinkedList<String> l1 = new LinkedList<>();
        LinkedList<String> l2 = new LinkedList<>();
        Map<String, Integer> m1 = new HashMap<>();
        Map<String, Integer> m2 = new HashMap<>();
        l1.add(beginWord);
        l2.add(endWord);
        m1.put(beginWord, 0);
        m2.put(endWord, 0);


        while (!l1.isEmpty() && !l2.isEmpty()) {
            int step;
            if (l1.size() <= l2.size()) {
                step = find(l1, m1, m2);
            } else {
                step = find(l2, m2, m1);
            }
            if (step > 0) {
                return step + 1;
            }
        }
        return 0;

    }

    private int find(LinkedList<String> list, Map<String, Integer> ma, Map<String, Integer> mb) {
        String poll = list.poll();

        char[] chars = poll.toCharArray();

        int length = chars.length;

        for (int i = 0; i < length; i++) {
            char c = chars[i];
            for (int j = 0; j < 26; j++) {
                chars[i] = (char) (j + 'a');
                String item = String.valueOf(chars);
                if (!set.contains(item)) {
                    continue;
                }
                if (ma.containsKey(item)) {
                    continue;
                }
                if (mb.containsKey(item)) {
                    return ma.get(poll) + mb.get(item) + 1;
                }
                ma.put(item, ma.get(poll) + 1);
                list.add(item);
            }
            chars[i] = c;
        }
        return -1;
    }

}
